// Copyright (C) 2024 EA group inc.
// Author: Jeff.li lijippy@163.com
// All rights reserved.
// This program is free software: you can redistribute it and/or modify
// it under the terms of the GNU Affero General Public License as published
// by the Free Software Foundation, either version 3 of the License, or
// (at your option) any later version.
//
// This program is distributed in the hope that it will be useful,
// but WITHOUT ANY WARRANTY; without even the implied warranty of
// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
// GNU Affero General Public License for more details.
//
// You should have received a copy of the GNU Affero General Public License
// along with this program.  If not, see <https://www.gnu.org/licenses/>.
//

#ifndef TURBO_NUMERIC_INTERNAL_BITS_H_
#define TURBO_NUMERIC_INTERNAL_BITS_H_

#include <cstdint>
#include <limits>
#include <type_traits>

// Clang on Windows has __builtin_clzll; otherwise we need to use the
// windows intrinsic functions.
#if defined(_MSC_VER) && !defined(__clang__)
#include <intrin.h>
#endif

#include <turbo/base/macros.h>

#if defined(__GNUC__) && !defined(__clang__)
// GCC
#define TURBO_NUMERIC_INTERNAL_HAVE_BUILTIN_OR_GCC(x) 1
#else
#define TURBO_NUMERIC_INTERNAL_HAVE_BUILTIN_OR_GCC(x) TURBO_HAVE_BUILTIN(x)
#endif

#if TURBO_NUMERIC_INTERNAL_HAVE_BUILTIN_OR_GCC(__builtin_popcountl) && \
    TURBO_NUMERIC_INTERNAL_HAVE_BUILTIN_OR_GCC(__builtin_popcountll)
#define TURBO_INTERNAL_CONSTEXPR_POPCOUNT constexpr
#define TURBO_INTERNAL_HAS_CONSTEXPR_POPCOUNT 1
#else
#define TURBO_INTERNAL_CONSTEXPR_POPCOUNT
#define TURBO_INTERNAL_HAS_CONSTEXPR_POPCOUNT 0
#endif

#if TURBO_NUMERIC_INTERNAL_HAVE_BUILTIN_OR_GCC(__builtin_clz) && \
    TURBO_NUMERIC_INTERNAL_HAVE_BUILTIN_OR_GCC(__builtin_clzll)
#define TURBO_INTERNAL_CONSTEXPR_CLZ constexpr
#define TURBO_INTERNAL_HAS_CONSTEXPR_CLZ 1
#else
#define TURBO_INTERNAL_CONSTEXPR_CLZ
#define TURBO_INTERNAL_HAS_CONSTEXPR_CLZ 0
#endif

#if TURBO_NUMERIC_INTERNAL_HAVE_BUILTIN_OR_GCC(__builtin_ctz) && \
    TURBO_NUMERIC_INTERNAL_HAVE_BUILTIN_OR_GCC(__builtin_ctzll)
#define TURBO_INTERNAL_CONSTEXPR_CTZ constexpr
#define TURBO_INTERNAL_HAS_CONSTEXPR_CTZ 1
#else
#define TURBO_INTERNAL_CONSTEXPR_CTZ
#define TURBO_INTERNAL_HAS_CONSTEXPR_CTZ 0
#endif

namespace turbo {
    TURBO_NAMESPACE_BEGIN
    namespace numeric_internal {

        constexpr bool IsPowerOf2(unsigned int x) noexcept {
            return x != 0 && (x & (x - 1)) == 0;
        }

        template<class T>
        TURBO_MUST_USE_RESULT TURBO_FORCE_INLINE constexpr T RotateRight(
                T x, int s) noexcept {
            static_assert(std::is_unsigned<T>::value, "T must be unsigned");
            static_assert(IsPowerOf2(std::numeric_limits<T>::digits),
                          "T must have a power-of-2 size");

            return static_cast<T>(x >> (s & (std::numeric_limits<T>::digits - 1))) |
                   static_cast<T>(x << ((-s) & (std::numeric_limits<T>::digits - 1)));
        }

        template<class T>
        TURBO_MUST_USE_RESULT TURBO_FORCE_INLINE constexpr T RotateLeft(
                T x, int s) noexcept {
            static_assert(std::is_unsigned<T>::value, "T must be unsigned");
            static_assert(IsPowerOf2(std::numeric_limits<T>::digits),
                          "T must have a power-of-2 size");

            return static_cast<T>(x << (s & (std::numeric_limits<T>::digits - 1))) |
                   static_cast<T>(x >> ((-s) & (std::numeric_limits<T>::digits - 1)));
        }

        TURBO_FORCE_INLINE TURBO_INTERNAL_CONSTEXPR_POPCOUNT int
        Popcount32(uint32_t x) noexcept {
#if TURBO_NUMERIC_INTERNAL_HAVE_BUILTIN_OR_GCC(__builtin_popcount)
            static_assert(sizeof(unsigned int) == sizeof(x),
                          "__builtin_popcount does not take 32-bit arg");
            return __builtin_popcount(x);
#else
            x -= ((x >> 1) & 0x55555555);
            x = ((x >> 2) & 0x33333333) + (x & 0x33333333);
            return static_cast<int>((((x + (x >> 4)) & 0xF0F0F0F) * 0x1010101) >> 24);
#endif
        }

        TURBO_FORCE_INLINE TURBO_INTERNAL_CONSTEXPR_POPCOUNT int
        Popcount64(uint64_t x) noexcept {
#if TURBO_NUMERIC_INTERNAL_HAVE_BUILTIN_OR_GCC(__builtin_popcountll)
            static_assert(sizeof(unsigned long long) == sizeof(x),  // NOLINT(runtime/int)
                          "__builtin_popcount does not take 64-bit arg");
            return __builtin_popcountll(x);
#else
            x -= (x >> 1) & 0x5555555555555555ULL;
            x = ((x >> 2) & 0x3333333333333333ULL) + (x & 0x3333333333333333ULL);
            return static_cast<int>(
                (((x + (x >> 4)) & 0xF0F0F0F0F0F0F0FULL) * 0x101010101010101ULL) >> 56);
#endif
        }

        template<class T>
        TURBO_FORCE_INLINE TURBO_INTERNAL_CONSTEXPR_POPCOUNT int
        Popcount(T x) noexcept {
            static_assert(std::is_unsigned<T>::value, "T must be unsigned");
            static_assert(IsPowerOf2(std::numeric_limits<T>::digits),
                          "T must have a power-of-2 size");
            static_assert(sizeof(x) <= sizeof(uint64_t), "T is too large");
            return sizeof(x) <= sizeof(uint32_t) ? Popcount32(x) : Popcount64(x);
        }

        TURBO_FORCE_INLINE TURBO_INTERNAL_CONSTEXPR_CLZ int
        CountLeadingZeroes32(uint32_t x) {
#if TURBO_NUMERIC_INTERNAL_HAVE_BUILTIN_OR_GCC(__builtin_clz)
            // Use __builtin_clz, which uses the following instructions:
            //  x86: bsr, lzcnt
            //  ARM64: clz
            //  PPC: cntlzd

            static_assert(sizeof(unsigned int) == sizeof(x),
                          "__builtin_clz does not take 32-bit arg");
            // Handle 0 as a special case because __builtin_clz(0) is undefined.
            return x == 0 ? 32 : __builtin_clz(x);
#elif defined(_MSC_VER) && !defined(__clang__)
            unsigned long result = 0;  // NOLINT(runtime/int)
            if (_BitScanReverse(&result, x)) {
              return 31 - result;
            }
            return 32;
#else
            int zeroes = 28;
            if (x >> 16) {
              zeroes -= 16;
              x >>= 16;
            }
            if (x >> 8) {
              zeroes -= 8;
              x >>= 8;
            }
            if (x >> 4) {
              zeroes -= 4;
              x >>= 4;
            }
            return "\4\3\2\2\1\1\1\1\0\0\0\0\0\0\0"[x] + zeroes;
#endif
        }

        TURBO_FORCE_INLINE TURBO_INTERNAL_CONSTEXPR_CLZ int
        CountLeadingZeroes16(uint16_t x) {
#if TURBO_HAVE_BUILTIN(__builtin_clzg)
            return x == 0 ? 16 : __builtin_clzg(x);
#elif TURBO_HAVE_BUILTIN(__builtin_clzs)
            static_assert(sizeof(unsigned short) == sizeof(x),  // NOLINT(runtime/int)
                          "__builtin_clzs does not take 16-bit arg");
            return x == 0 ? 16 : __builtin_clzs(x);
#else
            return CountLeadingZeroes32(x) - 16;
#endif
        }

        TURBO_FORCE_INLINE TURBO_INTERNAL_CONSTEXPR_CLZ int
        CountLeadingZeroes64(uint64_t x) {
#if TURBO_NUMERIC_INTERNAL_HAVE_BUILTIN_OR_GCC(__builtin_clzll)
            // Use __builtin_clzll, which uses the following instructions:
            //  x86: bsr, lzcnt
            //  ARM64: clz
            //  PPC: cntlzd
            static_assert(sizeof(unsigned long long) == sizeof(x),  // NOLINT(runtime/int)
                          "__builtin_clzll does not take 64-bit arg");

            // Handle 0 as a special case because __builtin_clzll(0) is undefined.
            return x == 0 ? 64 : __builtin_clzll(x);
#elif defined(_MSC_VER) && !defined(__clang__) && \
    (defined(_M_X64) || defined(_M_ARM64))
            // MSVC does not have __buitin_clzll. Use _BitScanReverse64.
            unsigned long result = 0;  // NOLINT(runtime/int)
            if (_BitScanReverse64(&result, x)) {
              return 63 - result;
            }
            return 64;
#elif defined(_MSC_VER) && !defined(__clang__)
            // MSVC does not have __buitin_clzll. Compose two calls to _BitScanReverse
            unsigned long result = 0;  // NOLINT(runtime/int)
            if ((x >> 32) &&
                _BitScanReverse(&result, static_cast<unsigned long>(x >> 32))) {
              return 31 - result;
            }
            if (_BitScanReverse(&result, static_cast<unsigned long>(x))) {
              return 63 - result;
            }
            return 64;
#else
            int zeroes = 60;
            if (x >> 32) {
              zeroes -= 32;
              x >>= 32;
            }
            if (x >> 16) {
              zeroes -= 16;
              x >>= 16;
            }
            if (x >> 8) {
              zeroes -= 8;
              x >>= 8;
            }
            if (x >> 4) {
              zeroes -= 4;
              x >>= 4;
            }
            return "\4\3\2\2\1\1\1\1\0\0\0\0\0\0\0"[x] + zeroes;
#endif
        }

        template<typename T>
        TURBO_FORCE_INLINE TURBO_INTERNAL_CONSTEXPR_CLZ int
        CountLeadingZeroes(T x) {
            static_assert(std::is_unsigned<T>::value, "T must be unsigned");
            static_assert(IsPowerOf2(std::numeric_limits<T>::digits),
                          "T must have a power-of-2 size");
            static_assert(sizeof(T) <= sizeof(uint64_t), "T too large");
            return sizeof(T) <= sizeof(uint16_t)
                   ? CountLeadingZeroes16(static_cast<uint16_t>(x)) -
                     (std::numeric_limits<uint16_t>::digits -
                      std::numeric_limits<T>::digits)
                   : (sizeof(T) <= sizeof(uint32_t)
                      ? CountLeadingZeroes32(static_cast<uint32_t>(x)) -
                        (std::numeric_limits<uint32_t>::digits -
                         std::numeric_limits<T>::digits)
                      : CountLeadingZeroes64(x));
        }

        TURBO_FORCE_INLINE TURBO_INTERNAL_CONSTEXPR_CTZ int
        CountTrailingZeroesNonzero32(uint32_t x) {
#if TURBO_NUMERIC_INTERNAL_HAVE_BUILTIN_OR_GCC(__builtin_ctz)
            static_assert(sizeof(unsigned int) == sizeof(x),
                          "__builtin_ctz does not take 32-bit arg");
            return __builtin_ctz(x);
#elif defined(_MSC_VER) && !defined(__clang__)
            unsigned long result = 0;  // NOLINT(runtime/int)
            _BitScanForward(&result, x);
            return result;
#else
            int c = 31;
            x &= ~x + 1;
            if (x & 0x0000FFFF) c -= 16;
            if (x & 0x00FF00FF) c -= 8;
            if (x & 0x0F0F0F0F) c -= 4;
            if (x & 0x33333333) c -= 2;
            if (x & 0x55555555) c -= 1;
            return c;
#endif
        }

        TURBO_FORCE_INLINE TURBO_INTERNAL_CONSTEXPR_CTZ int
        CountTrailingZeroesNonzero64(uint64_t x) {
#if TURBO_NUMERIC_INTERNAL_HAVE_BUILTIN_OR_GCC(__builtin_ctzll)
            static_assert(sizeof(unsigned long long) == sizeof(x),  // NOLINT(runtime/int)
                          "__builtin_ctzll does not take 64-bit arg");
            return __builtin_ctzll(x);
#elif defined(_MSC_VER) && !defined(__clang__) && \
    (defined(_M_X64) || defined(_M_ARM64))
            unsigned long result = 0;  // NOLINT(runtime/int)
            _BitScanForward64(&result, x);
            return result;
#elif defined(_MSC_VER) && !defined(__clang__)
            unsigned long result = 0;  // NOLINT(runtime/int)
            if (static_cast<uint32_t>(x) == 0) {
              _BitScanForward(&result, static_cast<unsigned long>(x >> 32));
              return result + 32;
            }
            _BitScanForward(&result, static_cast<unsigned long>(x));
            return result;
#else
            int c = 63;
            x &= ~x + 1;
            if (x & 0x00000000FFFFFFFF) c -= 32;
            if (x & 0x0000FFFF0000FFFF) c -= 16;
            if (x & 0x00FF00FF00FF00FF) c -= 8;
            if (x & 0x0F0F0F0F0F0F0F0F) c -= 4;
            if (x & 0x3333333333333333) c -= 2;
            if (x & 0x5555555555555555) c -= 1;
            return c;
#endif
        }

        TURBO_FORCE_INLINE TURBO_INTERNAL_CONSTEXPR_CTZ int
        CountTrailingZeroesNonzero16(uint16_t x) {
#if TURBO_HAVE_BUILTIN(__builtin_ctzg)
            return __builtin_ctzg(x);
#elif TURBO_HAVE_BUILTIN(__builtin_ctzs)
            static_assert(sizeof(unsigned short) == sizeof(x),  // NOLINT(runtime/int)
                          "__builtin_ctzs does not take 16-bit arg");
            return __builtin_ctzs(x);
#else
            return CountTrailingZeroesNonzero32(x);
#endif
        }

        template<class T>
        TURBO_FORCE_INLINE TURBO_INTERNAL_CONSTEXPR_CTZ int
        CountTrailingZeroes(T x) noexcept {
            static_assert(std::is_unsigned<T>::value, "T must be unsigned");
            static_assert(IsPowerOf2(std::numeric_limits<T>::digits),
                          "T must have a power-of-2 size");
            static_assert(sizeof(T) <= sizeof(uint64_t), "T too large");
            return x == 0 ? std::numeric_limits<T>::digits
                          : (sizeof(T) <= sizeof(uint16_t)
                             ? CountTrailingZeroesNonzero16(static_cast<uint16_t>(x))
                             : (sizeof(T) <= sizeof(uint32_t)
                                ? CountTrailingZeroesNonzero32(
                                            static_cast<uint32_t>(x))
                                : CountTrailingZeroesNonzero64(x)));
        }

        // If T is narrower than unsigned, T{1} << bit_width will be promoted.  We
        // want to force it to wraparound so that bit_ceil of an invalid value are not
        // core constant expressions.
        template<class T>
        TURBO_FORCE_INLINE TURBO_INTERNAL_CONSTEXPR_CLZ
        typename std::enable_if<std::is_unsigned<T>::value, T>::type
        BitCeilPromotionHelper(T x, T promotion) {
            return (T{1} << (x + promotion)) >> promotion;
        }

        template<class T>
        TURBO_FORCE_INLINE TURBO_INTERNAL_CONSTEXPR_CLZ
        typename std::enable_if<std::is_unsigned<T>::value, T>::type
        BitCeilNonPowerOf2(T x) {
            // If T is narrower than unsigned, it undergoes promotion to unsigned when we
            // shift.  We calculate the number of bits added by the wider type.
            return BitCeilPromotionHelper(static_cast<T>(std::numeric_limits<T>::digits - CountLeadingZeroes(x)),
                                          T{sizeof(T) >= sizeof(unsigned) ? 0 : std::numeric_limits<unsigned>::digits -
                                                                                std::numeric_limits<T>::digits});
        }

    }  // namespace numeric_internal
    TURBO_NAMESPACE_END
}  // namespace turbo

#endif  // TURBO_NUMERIC_INTERNAL_BITS_H_
